Why is an Array Ideal for Representing a Heap?
- Recall from our discussion on binary trees (Lecture 5, Slide 14) that they can be stored in two main ways: a linked structure or an array.
- While flexible, a linked representation has overhead from storing pointers. An array is more compact but can be very wasteful for unbalanced or skewed trees, leaving many empty slots.
- However, a heap is a complete binary tree. This property guarantees that there will be no gaps when we store the nodes in an array using a level-order traversal.
- This makes the array a highly efficient and compact way to store a heap. We can find any node's parent or children using simple arithmetic instead of pointers.
Array Indexing Rules (for a node at index $i$)
Its parent is at index: $ \lfloor (i - 1) / 2 \rfloor $
Its left child is at index: $ 2 \times i + 1 $
Its right child is at index: $ 2 \times i + 2 $